Formal Language Theory
----------------------

<!--
SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.

SPDX-License-Identifier: CC0-1.0
-->

[(Up)](../../README.md#topics) | _See also: [Attribute Grammars](../Attribute%20Grammars/README.md#attribute-grammars), [Parsing](../Parsing/README.md#parsing)_

- - - -


### Web resources

[Definite clause grammar - Wikipedia](https://en.wikipedia.org/wiki/Definite_clause_grammar)

[Context-free grammar - Wikipedia](https://en.wikipedia.org/wiki/Context-free_grammar)

[Context-sensitive grammar - Wikipedia](https://en.wikipedia.org/wiki/Context-sensitive_grammar)

[Mildly context-sensitive grammar formalism - Wikipedia](https://en.wikipedia.org/wiki/Mildly_context-sensitive_grammar_formalism)

[Literal movement grammar - Wikipedia](https://en.wikipedia.org/wiki/Literal_movement_grammar)

[Range concatenation grammar - Wikipedia](https://en.wikipedia.org/wiki/Range_concatenation_grammar)

[Star height problem - Wikipedia, the free encyclopedia](https://en.wikipedia.org/wiki/Star_height_problem)

[finite automata - Is there a reasonable and studied concept of reduction between regular languages? - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/106297/is-there-a-reasonable-and-studied-concept-of-reduction-between-regular-languages) ★

[parsers - Representing \"but not\" in formal grammar - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/122045/representing-but-not-in-formal-grammar) ★

[formal languages - Proving that a word is \*not\* generated by a context-free grammar - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/23609/proving-that-a-word-is-not-generated-by-a-context-free-grammar) ★

[closure properties - Does there exist an context free language L such that L∩L\^R is not context free? - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/163023/does-there-exist-an-context-free-language-l-such-that-l%e2%88%a9lr-is-not-context-free) ★

[computability - Context-free complete language - Computer Science Stack Exchange](https://cs.stackexchange.com/questions/99477/context-free-complete-language) ★★★

[Natural examples of context-sensitive languages from practice - Theoretical Computer Science Stack Exchange](https://cstheory.stackexchange.com/questions/25066/natural-examples-of-context-sensitive-languages-from-practice) ★

[idioms - Is \"regex\" in modern programming languages really \"context sensitive grammar\"? - Stack Overflow](https://stackoverflow.com/questions/612654/is-regex-in-modern-programming-languages-really-context-sensitive-grammar) ★

_(in [Automata Theory](../Automata%20Theory/README.md#automata-theory))_ [Csc520 Foundations of Computer Science](https://web.archive.org/web/20161105235418/https://www.cs.wcupa.edu/rkline/csc520) ★

_(in [Programming Languages](../Programming%20Languages/README.md#programming-languages))_ [GF - Grammatical Framework](https://www.grammaticalframework.org/) ★

_(in [Programming Languages](../Programming%20Languages/README.md#programming-languages))_ [Grammatical Framework (programming language) - Wikipedia](https://en.wikipedia.org/wiki/Grammatical_Framework_(programming_language))


### Papers

[The Hardest Context-Free Language](https://epubs.siam.org/doi/10.1137/0202025) 🏛️ [💭](commentary/Chris%20Pressey.md#the-hardest-context-free-language)

[Lecture 7: Definite Clause Grammars](https://www.scss.tcd.ie/Tim.Fernando/LPN/PDFs/7.pdf) ★

On the Structure of Context-Sensitive Grammars (online @ [archive.org](https://archive.org/details/nasa_techdoc_19710024701)) ★★ [💭](commentary/Chris%20Pressey.md#on-the-structure-of-context-sensitive-grammars)

[Functional Unification Grammar](https://aclanthology.org/P84-1018.pdf)

[Definite Clause Grammars for Language Analysis](https://cgi.di.uoa.gr/~takis/pereira-warren.pdf) ★

[Formal Languages and Infinite Groups](https://arxiv.org/abs/math/9509204v1) ★ [💭](commentary/Chris%20Pressey.md#formal-languages-and-infinite-groups)

[Formal languages and groups as memory](https://arxiv.org/abs/math/0601061v2) ★ [💭](commentary/Chris%20Pressey.md#formal-languages-and-groups-as-memory)

_(in [Logic](../Logic/README.md#logic))_ The Galois Connection between Syntax and Semantics (online @ [www.logicmatters.net](https://www.logicmatters.net/2010/06/03/the-galois-connection-between-syntax-and-semantics/)) ★ [💭](commentary/Chris%20Pressey.md#the-galois-connection-between-syntax-and-semantics)


### Books

Introduction to Formal Languages (borrow @ [archive.org](https://archive.org/details/introductiontofo0000reve)) ★ [💭](commentary/Chris%20Pressey.md#introduction-to-formal-languages)

Natural Language Processing Techniques in Prolog (online @ [cs.union.edu](https://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/index.html)) ★ [💭](commentary/Chris%20Pressey.md#natural-language-processing-techniques-in-prolog)

Programs, Grammars, Arguments (online @ [archive.org](https://archive.org/details/flooved3381))

_(in [Linguistics](../Linguistics/README.md#linguistics))_ An Introduction to Unification-based Approaches to Grammar (online @ [dash.harvard.edu](https://dash.harvard.edu/bitstream/handle/1/11576719/shieber-uagf-distrib-130816_0.pdf)) (borrow @ [archive.org](https://archive.org/details/introductiontoun00shie)) ★